#include "main/utils.h"
#include "lib/binary_tree.h"
using namespace std;

using TreeNode = BinaryTreeNode;

class Solution {
  private:
    int ret = INT_MIN;
  public:
    int dfs(TreeNode* root) {
      if (!root) {
        return 0;
      }
      int left = max(dfs(root->left), 0);
      int right = max(dfs(root->right), 0);
      ret = max(left + root->value + right, ret);
      return root->value + max(left, right);
    }
    int maxPathSum(TreeNode* root) {
      dfs(root);
      return ret;
    }
};

int main() {
  BinaryTreeNode* node1 = CreateBinaryTreeNode(1);
  BinaryTreeNode* node2 = CreateBinaryTreeNode(2);
  BinaryTreeNode* node3 = CreateBinaryTreeNode(3);

  ConnectNode(node1, node2, node3);
  Solution su;
  cout << su.maxPathSum(node1) << endl;

  return 0;
}
